/*
*******************************************************************************
* ansi c source code
* file name:
*	SRFFT.c
* abstract:
*	complete the Split-Radix decimation_in frequency FFT with variable length
* author:Fangming He
*******************************************************************************
*/



/*
*******************************************************************************
*                               include files
*******************************************************************************
*/
#include <stdio.h>
#include <math.h>
#include <string.h>
#include "../common/globaldef.h"
#include "../common/bit_rev.h"
#include "../common/globalVai.h"


/*
*******************************************************************************
*                            function definition
*******************************************************************************
*/
/*
******************************************************************************* 
* description:
*   complete the Split-Radix decimation_in frequency FFT with variable length
*	input  : the original data need FFT
*	length : the size of FFT for power of 2
* ouput
*   the result of FFT also remains in input 
* author:
*	guo liang       2006-05-04
*******************************************************************************
*/

int SRFFT (struct Complex *input ,int length )
{
	struct Complex tmp;
	int round ;
	int distance1;
	int distance2;
	int distance3;
	int i_num;
	int i;
	int k;
	int j;
	int j_relevance;
	int l;
	int l_relevance;
	i_num = 1;
	k = 1;
	i = 1;
	for ( round = length ; round > 2 ; round >>= 1 )
	{
		distance1 = round / 2;
		distance2 = round / 4;
		distance3 = round * 2;
		for ( i = 0 ; i < distance2 ; i++)
		{
			j = i;
			distance3 = round * 2; 
			do
			{
				for ( ; j < length ; j +=distance3)
				{
					j_relevance =  j + distance1;
					tmp.real = input[j].real + input[j_relevance].real;
					tmp.imag = input[j].imag + input[j_relevance].imag;
					input[j_relevance].real = input[j].real - input[j_relevance].real;
					input[j_relevance].imag = input[j].imag - input[j_relevance].imag;
					input[j].real = tmp.real;
					input[j].imag = tmp.imag;
					l = j + distance2;
					l_relevance = l + distance1;
					tmp.imag = -input[l].real + input[l_relevance].real;
					tmp.real =  input[l].imag - input[l_relevance].imag;
					input[l].real = input[l].real + input[l_relevance].real;
					input[l].imag = input[l].imag + input[l_relevance].imag;
					input[l_relevance].real = tmp.real;
					input[l_relevance].imag = tmp.imag;
					tmp.real = input[j_relevance].real + input[l_relevance].real;
					tmp.imag = input[j_relevance].imag + input[l_relevance].imag;
					input[l_relevance].real = input[j_relevance].real - input[l_relevance].real;
					input[l_relevance].imag = input[j_relevance].imag - input[l_relevance].imag;
					input[j_relevance].real = tmp.real;
					input[j_relevance].imag = tmp.imag;
					if ( i != 0 )
					{
						input[j_relevance] = Mul_complex( input[j_relevance] , twiddle[k*i]);
						input[l_relevance] = Mul_complex( input[l_relevance] , twiddle[3*k*i]);
					}
				}
				j = 2*distance3 - round + i;
				distance3 = distance3 * 4; 
			}
			while (  j < length );
		}
		k = k << 1;
	}
	distance3 = 4;
	j = 0;
	do 
	{
		for ( ; j < length ; j += distance3)
		{
			j_relevance = j + 1;
			tmp.real = input[j].real + input[j_relevance].real;
			tmp.imag = input[j].imag + input[j_relevance].imag;
			input[j_relevance].real = input[j].real - input[j_relevance].real;
			input[j_relevance].imag = input[j].imag - input[j_relevance].imag;
			input[j].real = tmp.real;
			input[j].imag = tmp.imag;
		}
		j = 2*distance3 - 2;
		distance3 = distance3 << 2; 
	}
	while ( j < length );
	bit_rev ( input , length );
	return 1;
}






				

		
	
